Адміністрація вирішила продати даний сайт. За детальною інформацією звертайтесь за адресою: rozrahu@gmail.com

ПРЯМИЙ МЕТОД ДОСТУПУ ДО ФАЙЛІВ НА ЗОВНІШНІХ ЗАПАМ’ЯТОВУЮЧИХ ПРИСТРОЯХ.

Інформація про навчальний заклад

ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Системи автоматизованого проектуваня

Інформація про роботу

Рік:
2007
Тип роботи:
Лабораторна робота
Предмет:
Організація баз даних і знань
Група:
КН-4

Частина тексту файла

Міністерство освіти і науки України Національний університет «Львівська політехніка» Кафедра С А П Р З в і т про виконання лабораторної роботи №2 на тему: «ПРЯМИЙ МЕТОД ДОСТУПУ ДО ФАЙЛІВ НА ЗОВНІШНІХ ЗАПАМ’ЯТОВУЮЧИХ ПРИСТРОЯХ» З курсу: «Організація баз даних і знань» Виконав: ст. гр. КН-4 Львів 2007р. Мета роботи Розглянути органiзацiю i ведення файлiв прямого доступу; набути практичнi навички у програмуваннi алгоритмiв доступу хешуванням. 2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ 2.1. МЕТОД ПРЯМОГО ДОСТУПУ Головною особливiстю прямого методу доступу є взаємна однозначна вiдповiднiсть мiж ключем запису i його фiзичною адресою. Фiзичне розмiщення запису визначається безпосередньо iз значення ключа. Створивши файл прямого доступу i видiливши для нього необхiдну дiлянку пам’ятi, можна вставляти записи у будь-якi мiсця файла. Перевага такого пiдходу над послiдовною органiзацiєю файла полягає у тому, що вдається отримати запис за заданим значенням ключа без попереднього перегляду всiх попереднiх записiв файла. ЕФЕКТИВНІСТЬ ДОСТУПУ дорiвнює одиницi. ЕФЕКТИВНІСТЬ ЗБЕРІГАННЯ залежить вiд густини ключiв. Якщо густина низька, пам’ять використовується неефективно, оскiльки резервуються адреси, що вiдповiдають вiдсутнiм ключам. У цьому випадку доцiльно використовувати для органiзацiї файла метод хешування. Пряму адресацiю можна важати частковим випадком методу хешування. 2.2. МЕТОДИ ХЕШУВАННЯ. На практицi кiлькiсть можливих значень ключiв набагато перевищує кiлькiсть реально присутнiх у будь-який момент значень цього ключа. У цьому випадку пряма адресацiя є невигiдною, оскiльки надто багато пам’ятi резервується для записiв, яких немає i нiколи не буде у файлi. Метод хешування дає змогу уникнути цього i водночас зберегти ефективнiсть, властиву прямiй адресацiї. На основi iнформацiї про множину фактичних значень ключiв створюється файл прямого доступу з такою кiлькiстю записiв, яка дещо перевищує фактичне значення ключiв. Вибирається функцiя хешування, яка перетворює значення ключа кожного запису в адресу блока у файлi. Зрозумiло, що хеш-функцiя h - це функцiя, яка вiдображає принцип "багато в один". 2.2.1. ПОШУК Для того щоб за даним значенням ключа k знайти вiдповiдний запис, необхiдно визначити h(k) i потiм органiзувати лiнiйний пошук у блоцi, номер якого дорiвнює h(k). Цей пошук буде продовжуватися доти, поки не буде знайдений запис, значення первинного ключа якого збiгається iз заданим. 2.2.2. ВСТАВЛЯННЯ Щоб вставити у файл новий запис, потрiбно за допомогою методу лiнiйного пошуку у блоцi, номер якого визначається значенням h(k), знайти вiльне мiсце. Пiсля цього на мiсце знайденого вiльного запису необхiдно розмiстити новий. Якщо при спробi помiстити новий запис у файл виявляється, що у знайденому блоцi немає вiльного мiсця, вважають, що блок переповнений. 2.2.3. ВИДАЛЕННЯ Для видалення запису iз файла потрiбно, використовуючи метод лiнiйного пошуку, знайти запис у блоцi, номер якого дорiвнює h(k). Якщо запис буде знайдено то вiн видаляється, якщо нi, то очевидно, що блок був переповнений i необхiдно продовжити пошук. 2.2.4. МОДИФІКАЦІЯ Якщо необхiдно модифiкувати запис, то потрiбно знайти цей запис i замiнити старi поля на новi. Нiяких iнших змiн не потрiбно. ХЕШ-функція 0 1 2 3 4 5 6 7 8 9 10 К1 К12 Рис.1. Ілюстрацiя методу хешування 2.3. ПЕРЕПОВНЕННЯ Для боротьби з переповненням можуть бути використанi три методи: зв’язаних блокiв, зв’язаних записiв та прогресуючого переповнення. 3.1. Метод блокiв, зв’язаних у ланцюг, полягає у такому. Коли блок переповнюється, у ньому розмiщується вказiвник на новостворений блок, призначений тiльки для записiв, що не помiстилися до першого блока. Якщо ж новостворений блок, своєю чергою, переповнений, у нього розмiщується вказiвник, що посилається на ще один знову створений блок i т.д. У результатi буде створений зв’язаний список блокiв, для всiх записiв якого значення функцiї хешування однакове. Головний недолiк методу зв’заних блокiв по...
Антиботан аватар за замовчуванням

01.01.1970 03:01

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Завантаження файлу

Якщо Ви маєте на своєму комп'ютері файли, пов'язані з навчанням( розрахункові, лабораторні, практичні, контрольні роботи та інше...), і Вам не шкода ними поділитись - то скористайтесь формою для завантаження файлу, попередньо заархівувавши все в архів .rar або .zip розміром до 100мб, і до нього невдовзі отримають доступ студенти всієї України! Ви отримаєте грошову винагороду в кінці місяця, якщо станете одним з трьох переможців!
Стань активним учасником руху antibotan!
Поділись актуальною інформацією,
і отримай привілеї у користуванні архівом! Детальніше

Оголошення від адміністратора

Антиботан аватар за замовчуванням

пропонує роботу

Admin

26.02.2019 12:38

Привіт усім учасникам нашого порталу! Хороші новини - з‘явилась можливість кожному заробити на своїх знаннях та вміннях. Тепер Ви можете продавати свої роботи на сайті заробляючи кошти, рейтинг і довіру користувачів. Потрібно завантажити роботу, вказати ціну і додати один інформативний скріншот з деякими частинами виконаних завдань. Навіть одна якісна і всім необхідна робота може продатися сотні разів. «Головою заробляти» продуктивніше ніж руками! :-)

Новини